{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Rearrange Sticks With K Sticks Visible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rearrangeSticks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #恰有 K 根木棍可以看到的排列数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 根长度互不相同的木棍，长度为从 <code>1</code> 到 <code>n</code> 的整数。请你将这些木棍排成一排，并满足从左侧 <strong>可以看到</strong> <strong>恰好</strong> <code>k</code> 根木棍。从左侧 <strong>可以看到</strong> 木棍的前提是这个木棍的 <strong>左侧</strong> 不存在比它 <strong>更长的</strong> 木棍。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果木棍排列为 <code>[<em><strong>1</strong></em>,<em><strong>3</strong></em>,2,<em><strong>5</strong></em>,4]</code> ，那么从左侧可以看到的就是长度分别为 <code>1</code>、<code>3</code> 、<code>5</code> 的木棍。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你 <code>n</code> 和 <code>k</code> ，返回符合题目要求的排列 <strong>数目</strong> 。由于答案可能很大，请返回对 <code>10<sup>9</sup> + 7</code> <strong>取余 </strong>的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, k = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>[<strong><em>1</em></strong>,<strong><em>3</em></strong>,2], [<em><strong>2</strong></em>,<em><strong>3</strong></em>,1] 和 [<em><strong>2</strong></em>,1,<em><strong>3</strong></em>] 是仅有的能满足恰好 2 根木棍可以看到的排列。\n",
    "可以看到的木棍已经用粗体+斜体标识。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, k = 5\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>[<em><strong>1</strong></em>,<em><strong>2</strong></em>,<em><strong>3</strong></em>,<em><strong>4</strong></em>,<em><strong>5</strong></em>] 是唯一一种能满足全部 5 根木棍可以看到的排列。\n",
    "可以看到的木棍已经用粗体+斜体标识。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 20, k = 11\n",
    "<strong>输出：</strong>647427950\n",
    "<strong>解释：</strong>总共有 647427950 (mod 10<sup>9 </sup>+ 7) 种能满足恰好有 11 根木棍可以看到的排列。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-rearrange-sticks-with-k-sticks-visible](https://leetcode.cn/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-rearrange-sticks-with-k-sticks-visible](https://leetcode.cn/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n2', '5\\n5', '20\\n11']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        f = [1] + [0] * k\n",
    "        for i in range(1, n + 1):\n",
    "            g = [0] * (k + 1)\n",
    "            for j in range(1, k + 1):\n",
    "                g[j] = (f[j] * (i - 1) + f[j - 1]) % mod\n",
    "            f = g\n",
    "        \n",
    "        return f[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        M = 10**9 + 7\n",
    "        # # f_ij: (j+1) visible for the LAST (i+1) sticks\n",
    "        # f = [[0]*k for _ in range(n)]\n",
    "        # f[0][0] = 1\n",
    "        \n",
    "        # for i in range(1, n):\n",
    "        #     f[i][0] = f[i-1][0] * i % M     # math.perm(i)\n",
    "        #     for j in range(1, min(k, i+1)):\n",
    "        #         f[i][j] = f[i-1][j-1] + f[i-1][j] * i\n",
    "        #         f[i][j] %= M\n",
    "        # return f[-1][-1] % M\n",
    "\n",
    "        # consider stick n, n-1, ..., 1\n",
    "        # g_i: number of sticks visible\n",
    "        g = [0] * (k+1)\n",
    "        g[1] = 1\n",
    "        for i in range(n-1, 0, -1):\n",
    "            g = [0] + [(g[j-1] + g[j] * (n-i)) % M for j in range(1, k+1)]\n",
    "        return g[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        f=[0]*(k+1)\n",
    "        f[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(min(i,k),0,-1):\n",
    "                f[j]=(f[j-1]+f[j]*(i-1))%mod\n",
    "        return f[k]\n",
    "        # @cache\n",
    "        # def dfs(i,j):#从大到小放，i根木棍，可以看见j根的方案数\n",
    "        #     if i==1:\n",
    "        #         return int(j==1)\n",
    "        #     ans=dfs(i-1,j-1)+dfs(i-1,j)*(i-1)\n",
    "        #     ans%=mod\n",
    "        #     return ans\n",
    "        # return dfs(n,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        M = 10**9 + 7\n",
    "        # # f_ij: (j+1) visible for the LAST (i+1) sticks\n",
    "        # f = [[0]*k for _ in range(n)]\n",
    "        # f[0][0] = 1\n",
    "        \n",
    "        # for i in range(1, n):\n",
    "        #     f[i][0] = f[i-1][0] * i % M     # math.perm(i)\n",
    "        #     for j in range(1, min(k, i+1)):\n",
    "        #         f[i][j] = f[i-1][j-1] + f[i-1][j] * i\n",
    "        #         f[i][j] %= M\n",
    "        # return f[-1][-1] % M\n",
    "\n",
    "        # consider stick n, n-1, ..., 1\n",
    "        g = [0] * (k+1)\n",
    "        g[1] = 1    # last stick\n",
    "        for i in range(n-1, 0, -1):\n",
    "            g = [0] + [(g[j-1] + g[j] * (n-i)) % M for j in range(1, k+1)]\n",
    "        return g[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\r\n",
    "        dp = [0] * (k + 1)\r\n",
    "        dp[0] = 1\r\n",
    "        for i in range(n - 1):\r\n",
    "            for j in range(min(k, i + 1), 0, -1):\r\n",
    "                dp[j] = (dp[j - 1] + dp[j] * i) % 1000000007\r\n",
    "            dp[0] = 0\r\n",
    "        \r\n",
    "        return (dp[k - 1] + dp[k] * (n - 1)) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(k, i), -1, -1):\n",
    "                # 不选，当前数能放到n - i个数的后面\n",
    "                dp[j] = dp[j] * (n - i)\n",
    "                # 选，则由dp[j - 1]转移过来\n",
    "                if j: dp[j] = (dp[j] + dp[j - 1]) % MOD\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        dp = [[0]*(k+1) for _ in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,k+1):\n",
    "                dp[i][j] = (dp[i-1][j-1] + (i-1)*dp[i-1][j])%1000000007\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [[0] * 1010 for _ in range(1010)]\n",
    "mod = 10**9 + 7\n",
    "dp[0][0] = 1\n",
    "for i in range(1, 1001):\n",
    "    for j in range(1, 1001):\n",
    "        dp[i][j] = (dp[i - 1][j - 1] + (i - 1) * dp[i - 1][j]) % mod\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[n][1] = 1\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = dp[i + 1][j - 1] + (n - i) * dp[i + 1][j]\n",
    "                dp[i][j] %= mod\n",
    "        # print(dp)\n",
    "        return dp[1][k] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MOD = int(1E9 + 7)\n",
    "\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        # 第一类斯特林数\n",
    "        if k == n:\n",
    "            return 1\n",
    "        \n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1) % self.MOD\n",
    "                dp[i][j] %= self.MOD\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [[0] * 1010 for _ in range(1010)]\n",
    "mod = 10**9 + 7\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = (dp[i - 1][j - 1] + (i - 1) * dp[i - 1][j]) % mod\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        M = 10**9 + 7\n",
    "        # f_ij: (j+1) visible for the LAST (i+1) sticks\n",
    "        f = [[0]*k for _ in range(n)]\n",
    "        f[0][0] = 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            f[i][0] = f[i-1][0] * i % M     # math.perm(i)\n",
    "            for j in range(1, min(k, i+1)):\n",
    "                f[i][j] = f[i-1][j-1] + f[i-1][j] * i\n",
    "                f[i][j] %= M\n",
    "        return f[-1][-1] % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[n][1] = 1\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] += dp[i + 1][j - 1] + (n - i) * dp[i + 1][j]\n",
    "                dp[i][j] %= mod\n",
    "        # print(dp)\n",
    "        return dp[1][k] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        dp, MOD = [[0] * (k + 1) for _ in range(n + 1)], 10 ** 9 + 7\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(k, i) + 1):\n",
    "                dp[i][j] = (dp[i - 1][j - 1] + (dp[i - 1][j] * (i - 1))) % MOD\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        dp = [[0] * (k+1) for _ in range(n+1)]\n",
    "        a = [1]\n",
    "        t = 1\n",
    "        for i in range(1, 1001):\n",
    "            t = (t * i) % MOD\n",
    "            a.append(t)\n",
    "        for i in range(1, n+1):\n",
    "            if i <= k:\n",
    "                dp[i][i] = 1\n",
    "            dp[i][1] = a[i - 1]\n",
    "        # print(dp)\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(2, k+1):\n",
    "                dp[i][j] = (dp[i-1][j-1] + (i-1) * dp[i-1][j]) % MOD\n",
    "        return dp[n][k]\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        # dp[i][j] 表示有 i 根木棍，从左侧可以看到 j 根木棍的排列数\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[1][1] = 1\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (i-1)) % MOD\n",
    "\n",
    "        return dp[n][k]\n",
    "\n",
    "# 示例\n",
    "solution = Solution()\n",
    "print(solution.rearrangeSticks(3, 2))  # 输出：3\n",
    "print(solution.rearrangeSticks(5, 5))  # 输出：1\n",
    "print(solution.rearrangeSticks(20, 11))  # 输出：647427950\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        f = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                f[i][j] = f[i - 1][j - 1]\n",
    "                if i - 1 >= j:    \n",
    "                    f[i][j] = (f[i][j] +  (i - 1) * f[i - 1][j]) % mod\n",
    "        return f[n][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        # not_used = set(range(1, n + 1))\n",
    "        # 被选中 有些直接就可以不用看了 哪些元素可以选\n",
    "        # 一个棍子往前 一个棍子往后\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        dp[1][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, min(k, i) + 1):\n",
    "                dp[i][j] = dp[i-1][j-1]\n",
    "                dp[i][j] += dp[i-1][j]*(i-1)\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if j == 0:\n",
    "                return 0\n",
    "\n",
    "            return (dfs(i - 1, j - 1) + (i - 1) * dfs(i - 1, j)) % kmod\n",
    "\n",
    "        ans = dfs(n, k)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Combinatorics:\n",
    "    def __init__(self, n, mod):\n",
    "        # 模板：求全排列组合数，使用时注意 n 的取值范围\n",
    "        n += 10\n",
    "        self.perm = [1] * n\n",
    "        self.rev = [1] * n\n",
    "        self.mod = mod\n",
    "        for i in range(1, n):\n",
    "            # 阶乘数 i! 取模\n",
    "            self.perm[i] = self.perm[i - 1] * i\n",
    "            self.perm[i] %= self.mod\n",
    "        self.rev[-1] = self.mod_reverse(self.perm[-1], self.mod)  # 等价于pow(self.perm[-1], -1, self.mod)\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            self.rev[i] = (self.rev[i + 1] * (i + 1) % mod)  # 阶乘 i! 取逆元\n",
    "        self.fault = [0] * n\n",
    "        self.fault_perm()\n",
    "        return\n",
    "\n",
    "    def ex_gcd(self, a, b):\n",
    "        # 扩展欧几里得求乘法逆元\n",
    "        if b == 0:\n",
    "            return 1, 0, a\n",
    "        else:\n",
    "            x, y, q = self.ex_gcd(b, a % b)\n",
    "            x, y = y, (x - (a // b) * y)\n",
    "            return x, y, q\n",
    "\n",
    "    def mod_reverse(self, a, p):\n",
    "        x, y, q = self.ex_gcd(a, p)\n",
    "        if q != 1:\n",
    "            raise Exception(\"No solution.\")  # 逆元要求a与p互质\n",
    "        else:\n",
    "            return (x + p) % p  # 防止负数\n",
    "\n",
    "    def comb(self, a, b):\n",
    "        if a < b:\n",
    "            return 0\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a] * self.rev[b] * self.rev[a - b]\n",
    "        return res % self.mod\n",
    "\n",
    "    def factorial(self, a):\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a]\n",
    "        return res % self.mod\n",
    "\n",
    "    def fault_perm(self):\n",
    "        # 求错位排列组合数\n",
    "        self.fault[0] = 1\n",
    "        self.fault[2] = 1\n",
    "        for i in range(3, len(self.fault)):\n",
    "            self.fault[i] = (i - 1) * (self.fault[i - 1] + self.fault[i - 2])\n",
    "            self.fault[i] %= self.mod\n",
    "        return\n",
    "\n",
    "    def inv(self, n):\n",
    "        # 求 pow(n, -1, mod)\n",
    "        return self.perm[n - 1] * self.rev[n] % self.mod\n",
    "\n",
    "    def catalan(self, n):\n",
    "        # 求卡特兰数\n",
    "        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod\n",
    "\n",
    "cb = Combinatorics(1001, mod)\n",
    "\n",
    "\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(n, k):\n",
    "    if n == k:\n",
    "        return 1\n",
    "    if k == 1:\n",
    "        return cb.factorial(n - 1)\n",
    "    return ((n-1)*dfs(n-1, k)+dfs(n-1, k-1)) % mod\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "        return dfs(n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeSticks(self, n: int, k: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(n, k):\n",
    "            if n == k:\n",
    "                return 1\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            return (dfs(n - 1, k - 1) + dfs(n - 1, k) * (n - 1)) % mod\n",
    "        \n",
    "        return dfs(n, k)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
